#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m = 100000, a[100001], c[100001], r[100001];

inline void countingsort() {
	memset(c, 0, sizeof(c));
	for (ll i = 1; i <= n; ++i)
		++c[a[i]];
	for (ll i = 1; i <= m; ++i)
		for (ll j = 1; j <= c[i]; ++j)
			printf("%lld ", i);
	printf("\n");
	for (ll i = 2; i <= m; ++i)
		c[i] += c[i - 1];
	for (ll i = n; i; i--)
		r[i] = c[a[i]]--;
	for (ll i = 1; i <= n; ++i)
		printf("%lld ", r[i]);
	printf("\n");
}

int main() {
	scanf("%lld", &n);
	for (ll i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);
	countingsort();
	return 0;
} 
